﻿using System;
using System.ComponentModel;
using System.Linq;
using ProjectEuler.Extensions;
using ProjectEuler.Linq;
using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace ProjectEuler.Problems
{
    [EulerProblem(33, 100)]
    [Description("Discover all the fractions with an unorthodox cancelling method.")]
    internal sealed class Problem033 : EulerProblem
    {
        public override Object Solve()
        {
            return (from combination in Combinations.All((10).To(99), 2)
                    let fraction = new Rational(combination[0], combination[1])
                    let lowest = fraction.ToLowestTerms()
                    let multiples = Multiples(lowest, fraction)
                    let simplifications = Simplifications(fraction)
                    where
                       simplifications.Any(s => IsUnorthodoxCancelling(fraction, s)) ||
                       multiples.Any(m => IsUnorthodoxCancelling(fraction, m))
                    select lowest)
                     .Product()
                     .ToLowestTerms()
                     .Denominator;
        }

        private static Boolean IsUnorthodoxCancelling(Rational fraction, Rational simpler)
        {
            if (fraction != simpler)
            {
                if (fraction.Denominator != (10 * simpler.Denominator))
                {
                    var numTens = (Int32)Math.Floor(fraction.Numerator / 10.0);
                    var numUnits = fraction.Numerator % (10 * numTens);

                    var denomTens = (Int32)Math.Floor(fraction.Denominator / 10.0);
                    var denomUnits = fraction.Denominator % (10 * denomTens);

                    return
                        (numUnits == denomTens) &&
                        (numTens == simpler.Numerator) &&
                        (denomUnits == simpler.Denominator);
                }
            }

            return false;
        }

        private static IEnumerable<Rational> Multiples(Rational lowest, Rational max)
        {
            var sieve = new SieveOfEratosthenes(Math.Max(max.Numerator, max.Denominator));

            foreach (var prime in sieve)
            {
                var r = lowest;

                while ((r.Numerator <= max.Numerator) && (r.Denominator <= max.Denominator))
                {
                    yield return r = new Rational(r.Numerator * prime, r.Denominator * prime);
                }
            }
        }

        private static IEnumerable<Rational> Simplifications(Rational r)
        {
            var sieve = new SieveOfEratosthenes(Math.Min(r.Numerator, r.Denominator));

            foreach (var prime in sieve)
            {
                while (((r.Numerator % prime) == 0) && ((r.Denominator % prime) == 0))
                {
                    yield return r = new Rational(r.Numerator / prime, r.Denominator / prime);
                }
            }
        }
    }
}
